import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] meetings = {{1,4,3},{0,4,3}};
        for(int e: s.findAllPeople(5,meetings,3)) {
            System.out.print(e + " ");
        }
    }

    public int removeStones(int[][] stones) {
        /**
         * 移除最多的同行或同列石头*/
        // 1 预处理
        int m = stones.length;
        // -给石头编号<二维编号，石头编号>
        int num = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int[] e: stones) {
            map.put(e[0]*1_0000+e[1], num++);
        }
        // -并查集初始化
        initialize(m);

        // 2 合并石头
        for(int i = 0; i < m-1; i++) {
            for(int j = i+1; j < m; j++) {
                int front = map.get(stones[i][0]*1_0000+stones[i][1]);
                int back = map.get(stones[j][0]*1_0000+stones[j][1]);
                if((stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) && !isSameSet(front, back)) {
                    union(front, back);
                    // -集合减一
                    num --;
                }
            }
        }

        // 3 返回值
        // -假设num个集合，每个集合至多消除size()-1，那么总共消除就是all-num
        return m - num;
    }

    // 并查集实现
    public static int MAX_N = 0;
    public static int[] father;
    public static int[] size;
    public static int[] stack;

    public static void initialize(int n) {
        // -1 分配空间
        MAX_N = n;
        father = new int[MAX_N];
        size = new int[MAX_N];
        stack = new int[MAX_N];

        // -2 初始化
        for(int i = 0; i < MAX_N; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int a) {
        /**
         * 找到a元素所在集合的代表元素，并做扁平化处理*/
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }
        while(i > 0) {
            father[stack[--i]] = a;
        }
        return a;
    }

    public static boolean isSameSet(int a, int b) {
        /**
         * 判断a、b元素是否属于同一集合*/
        return find(a) == find(b);
    }

    public static void union(int a, int b) {
        /**
         * 合并a、b元素所在集合，并做小挂大优化*/
        int fa = find(a);
        int fb = find(b);
        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                size[fa] += size[fb];
                father[fb] = fa;
            } else {
                size[fb] += size[fa];
                father[fa] = fb;
            }
        }
    }

    // 知情人容器
    public static Set<Integer> set;
    // 暂存箱容器
    public static Map<Integer, List<Integer>> ts = new HashMap<>();

    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        /**
         * 找出知晓秘密的所有专家*/
        // 1 预处理
        // -数据按照时间排序
        Arrays.sort(meetings, (a, b) -> a[2] - b[2]);
        // -存储知情人容器初始化
        set = new HashSet<>();
        set.add(0);
        set.add(firstPerson);
        // -设置当前时间
        int curTime = 0;

        // 2 遍历
        for(int[] e: meetings) {
            int a = e[0];
            int b = e[1];

            // -1 根据时间设置暂存容器
            if(curTime != e[2]) {
                ts = new HashMap<>();
                curTime = e[2];
            }

            // -2 查询本场会议是否有知情人（有则入容器，无则入暂存，每次入容器时需要判断暂存）
            if(set.contains(a)) {
                set.add(b);
                // -新入值去更新暂存
                updateTemporaryStorage(b);
            } else if(set.contains(b)) {
                set.add(a);
                // -新入值去更新暂存
                updateTemporaryStorage(a);
            } else {
                // -入暂存
                if(!ts.containsKey(a)) {
                    ts.put(a, new ArrayList<>());
                }
                if(!ts.containsKey(b)) {
                    ts.put(b, new ArrayList<>());
                }
                ts.get(a).add(b);
                ts.get(b).add(a);
            }
        }

        // 3 返回值
        return new LinkedList<>(set);
    }

    public static void updateTemporaryStorage(int a) {
        /**
         * 更新暂存箱*/
        // 1 判断是否存在于暂存箱
        if(ts.containsKey(a)) {
            // 2 扩散
            for(int e: ts.get(a)) {
                if(!set.contains(e)) {
                    set.add(e);
                    updateTemporaryStorage(e);
                }
            }
        }
    }
}
